import java.util.Scanner;

//思想：把一万个数据进行模100000操作重新放到一个数组中
public class Main{
       public static void main(String[] args){
              Scanner sc=new Scanner(System.in);
              int[] arr=new long[100002];
              a[0]=1;
              a[1]=1;
              for(int i=2;i<arr.length;i++)
                   arr[i]=(arr[i-1]+arr[i-2])%1000000;   //只需输出后六位，故数字相加超过六位的进位就可以抛弃    
              }
              while (sc.hasNext()) {       
                    int n = sc.nextInt();     
                    System.out.printf((n<25?"%d\n":"%06d\n"), arr[n]); 
              }
       }
}
